package two.chapter_2.c2_4;

import two.chapter_2.c2_1.Sortable;

public class MyHeapSort<Item extends Comparable<Item>> extends Sortable<Item> {

    //1,使堆有序
    //2,依次取出剩余元素中最大元素
    @Override
    public void sort(Item[] items) {
        int N=items.length;
        //从最后一个元素的父元素开始，做下沉操作，使堆有序
        for (int k=N/2;k>=1;k--){
            sink(items,k,N);
        }

        while (N>1){
            exch(1,N--,items);
            sink(items,1,N);
        }
    }

    private void sink(Item[] items, int k, int N) {
        while (2*k<=N){
            int j=2*k;
            if (j< N && less(items,j,j+1)){
                j++;
            }

            if (!less(items,k,j)){
                break;
            }
            exch(k,j,items);
            k=j;
        }
    }

    public boolean less(Item[] items,int i,int j) {
        return items[i-1].compareTo(items[j-1])<0;
    }
    public void exch(int indexA,int indexB,Item[] items){
        Item t=items[indexA-1];
        items[indexA-1]=items[indexB-1];
        items[indexB-1]=t;
    }
}
